The present invention relates to techniques for analyzing a body of data. More specifically, the invention relates to techniques that analyze an image by finding near neighbors of pixels in the image.
Borgefors, G., "Distance Transformations in Digital Images," Computer Vision Graphics and Image Processing, Vol. 34 (1986), pp. 344-371, describes distance transformations that convert a binary digital image, consisting of feature and non-feature pixels, into an image where each non-feature pixel has a value corresponding to the distance to the nearest feature pixel. To compute the distances with global operations would be prohibitively costly; the paper describes digital distance transformation algorithms that use small neighborhoods and that give a reasonable approximation of distance. Page 345 explains that such algorithms are based on approximating global distances in the image by propagating local distances, i.e. distances between neighboring pixels. The distance transformations are described in graphical form as masks, as shown in FIG. 2; the local distance in each mask-pixel is added to the value of the image pixel below it and the minimum of the sums becomes the new image pixel value. Parallel computation of such a distance transformation requires a number of iterations proportional to the largest distance in the image. Section 3, beginning on page 347, describes optimal distance transformations for different image sizes. Section 4, beginning on page 362, compares several examples, including computing the distance from an object or object contour, in Section 4.3, and computing a pseudo-Dirichlet or Voronoi tessellation, in Section 4.4.
Ahuja, N., and Schachter, B. J., Pattern Models, John Wiley and Sons, New York, 1983, Chapter 1, pp. 1-73, describe tessellations beginning at page 4. Section 1.3.5, beginning on page 15, describes Voronoi and Delaunay tessellations, indicating that a Voronoi polygon is the locus of points closer to a vertex than to any other vertex and that the Delaunay triangulation is a dual of a Voronoi tessellation. Algorithms for constructing the Delaunay triangulation are described beginning at page 22. Section 1.3.5.4, beginning on page 32, describes the use of the Voronoi polygon for neighborhood definition, reviewing other techniques for defining the neighborhood of a point and comparing them with the Voronoi approach. FIGS. 1.3.5.4-2 shows how Voronoi neighbors of a point may be farther from it than nonneighbors, because Voronoi neighbors are not necessarily its nearest neighbors--the Voronoi neighbors of a point must surround it.
Mahoney, J. V., Image Chucking: Defining Spatial Building Blocks for Scene Analysis, Dep't. of Elec. Eng. and Comp. Sci., M.I.T., 1987 ("the Mahoney thesis"), pp. 31-37, describes techniques for detecting abrupt change boundaries by direct comparisons between neighboring elements. Pages 32-34 describe the directional nearest neighbor graph, useful for computing an explicit representation of the neighbors of each image property element, and compare it to the Voronoi dual.